package com.atguigu.search;

import java.util.Arrays;

/**
 * 斐波那契查找
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        // arr.length=16
        int[] arr={28, 180, 247, 279, 463, 483, 574, 596, 651, 709, 752, 1068, 1231, 1266, 1332, 1534};
        int search = search(arr, 1534);
        System.out.println("resIndex="+search);
    }

    public static final int FIBO_MAX_SIZE=20;

    // binary arr:[1, 2, 4, 8, 16, 32]
    // fibo arr:[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
    public static int[] fibo(){
        int[] arr=new int[FIBO_MAX_SIZE];
        arr[0]=1;
        arr[1]=1;

        for(int i=2;i<arr.length;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }

        return arr;
    }

    public static int search(int[] arr,int findVal){
        int leftIndex=0;
        int rightIndex=arr.length-1;
        // 斐波那契数值下标
        int fiboIndex=0;
        // 存放mid值->分割索引. 在斐波那契查找中, 分割索引总是等于斐波那契数列中大小值的加减所得. 且每一轮仅会添加一个额外的加减因子
        int divideIndex;

        // 获取斐波那契数列
        int[] fiboArr=fibo();
//        System.out.println("fibo arr:"+Arrays.toString(fiboArr));
        while(arr.length>fiboArr[fiboIndex]){
            fiboIndex++;
        }

        // 构建符合斐波那契数列某个值大小的数组
        // 按照此例, 原本大小为16的arr, 会被扩展为一个大小为21的数组tempArr
        int[] tempArr= Arrays.copyOf(arr,fiboArr[fiboIndex]);
        for(int i=rightIndex+1;i<tempArr.length;i++){
            tempArr[i]=tempArr[rightIndex];
        }

        // while循环找到findVal的索引
        /*
         * 实例模拟说明:
         * arr.length=16
         * tempArr.length=21=fibo[7]=fibo[6]+fibo[5]
         * fibo arr:[1, 1, 2, 3, 5, 8, 13, 21, ...]
         * fibo index:0, 1, 2, 3, 4, 5, 6, 7, ...
         * 第一轮:
         * fiboIndex: fibo[7]=fibo[6]+fibo[5], divideIndex=leftIndex+fibo[6]-1=0+13-1=12, 即第fibo[6]个数
         * 判断目标值比tempArr[12]大还是小.
         * 如果小, 则右边界收缩到11, fiboIndex: fibo[6]=fibo[5]+fibo[4], divideIndex=leftIndex+fibo[5]-1=0+8-1=7, 即第fibo[5]个数
         * 如果大, 则左边界收缩到13, fiboIndex: fibo[5]=fibo[4]+fibo[3], divideIndex=leftIndex+fibo[4]-1=13+5-1=17, 即第fibo[6]+fibo[4]个数
         * 如果相等, 情况说明如下:
         * 从第一轮开始, leftIndex,rightIndex,divideIndex均在原来的数组合法索引内.
         * 前两者分别是数组的左右边界,
         * 后者则由于fiboIndex是大于等于数组大小的最小的索引, 所以初次取到的次小值必定在数组范围内.
         * 此后, 每次右索引变化, 只会更小, 因此必定在边界内;
         * 左索引变化, 如果跨过右索引, 则直接跳出循环;
         * 因此, 如果切割索引偶然调到了原始数组右边界之外, 且命中目标值, 则最右索引也必定符合要求.
         * 事实上, 最后判定边界的右索引, 也可考虑用原始数组的边界大小来判定.
         *
         * 此后每轮搜索范围减少数量, 对应的fiboIndex, 要么是-1,要么是-2
         * 直到最后索引减到fiboIndex=0或fiboIndex=1时, 要么命中值, 要么直接退出(此时的搜索范围=1,任意的减少必定导致leftIndex>rightIndex)
         *
         * 本质是二分查找的一种变体, 从感觉上讲, 效率应该比如插值查找, 只是比较优雅.
         *
         */
        while(leftIndex<=rightIndex){
            // 第一次等于
            divideIndex=leftIndex+fiboArr[fiboIndex-1]-1;
            if(findVal<tempArr[divideIndex]){
                rightIndex=divideIndex-1;
                fiboIndex--;
            }else if(findVal>tempArr[divideIndex]){
                leftIndex=divideIndex+1;
                fiboIndex-=2;
            }else{
                // 需要确定, 返回的是哪个下标
                if(divideIndex<=rightIndex){
                    return divideIndex;
                }else{
                    return rightIndex;
                }
            }
        }



        return -1;
    }
}
